We could use data structures we already know to build a Priority Queue.
-
Unsorted Array/List
insert(): $O(1)$ - Just add to the end.extractMax(): $O(n)$ - Must search the entire list to find the max.
-
Sorted Array/List
insert(): $O(n)$ - Must shift elements to maintain order.extractMax(): $O(1)$ - It's at the end.
The Challenge
Can we do better? With these simple structures, one of the core operations is always slow. The goal is to find a data structure where both insertion and extraction are fast.
| Data Structure | insert() |
extractMax() |
|---|---|---|
| Unsorted Array | $O(1)$ | $O(n)$ |
| Sorted Array | $O(n)$ | $O(1)$ |